/*
 * @lc app=leetcode.cn id=430 lang=typescript
 *
 * [430] 扁平化多级双向链表
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     prev: Node | null
 *     next: Node | null
 *     child: Node | null
 *     constructor(val?: number, prev? : Node, next? : Node, child? : Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *         this.child = (child===undefined ? null : child);
 *     }
 * }
 */

function flatten(head: Node | null): Node | null {
  if (head === null) return null;
  let p = head;
  while (p) {
    if (p.child !== null) {
      let q = p.child;
      // 找到子链表的最后一个节点
      while (q.next) {
        q = q.next;
      }
      q.next = p.next;
      p.next && (p.next.prev = q);
      p.child.prev = p;
      p.next = p.child;
      p.child = null;
    }

    p = p.next;
  }

  return head;
}
// @lc code=end
